package algorithm.sort;

public class BitQuickSort extends Common implements Sort {
    QuickSort quickSort = new QuickSort(type);

    @Override
    public void execute(int[] nums) {
        execute(nums, type);
    }

    @Override
    public void execute(int[] nums, ImplementType methodType) {
        int maxIndex = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        int j = 1;
        for (; j < 32; j++) {
            if ((nums[maxIndex] & (1 << 32 - j)) >> (32 - j) == 1) {
                break;
            }
        }
        // System.out.println(j);
        quickSort(nums, 0, nums.length - 1, 1 << 32 - j);
    }

    public void quickSort(int[] nums, int left, int right, int pos) {
        if ((right - left) < 1 || pos == 0) {
            return;
        }
        // if ((right - left) < 33) {
        // quickSort.quickSort(nums, left, right);
        // }
        if (right - left == 1) {
            if (nums[right] < nums[left]) {
                nums[right] = nums[right] ^ nums[left];
                nums[left] = nums[right] ^ nums[left];
                nums[right] = nums[right] ^ nums[left];
            }
        }
        int sl = left;
        int sr = right;
        int first = nums[left];

        while (left < right) {
            for (; left < right && (nums[right] & pos) == pos; right--)// 找到一个为0的
                ;
            if (left < right) {
                nums[left] = nums[right];
            }
            for (; left < right && (nums[left] & pos) != pos; left++)// 找到一个为1的
                ;
            if (left < right) {
                nums[right] = nums[left];
            }
            if (left == right) {
                nums[left] = first;
                if ((nums[right] & pos) == pos) {// 放右边
                    right -= 1;
                } else {
                    left += 1;
                }
                break;
            }
        }
        quickSort(nums, sl, right, pos >> 1);
        quickSort(nums, left, sr, pos >> 1);
    }

}
